package 寒假作业.LeetCode;


import java.util.HashMap;
import java.util.Map;

public class Num1171 {
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
    public ListNode removeZeroSumSublists(ListNode head) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;

        Map<Integer,ListNode> map = new HashMap<>();
        int sum = 0;
        ListNode node = dummyHead;
        //map中存截至到当前节点的sum值总和和对应的后续链表
        //如果有相同的sum值则更新后续链表
        while (node != null) {
            sum += node.val;
            map.put(sum,node);
            node = node.next;
        }
        sum = 0;
        node = dummyHead;
        //第二次遍历从前向后走，如果取到的sum相同但是节点值不同
        //说明这两个节点之间的链表节点值的总和为0
        //删除区间节点
        while (node != null){
            sum += node.val;
            node.next = map.get(sum).next;
            node = node.next;
        }
        return dummyHead.next;
    }
}
